<h2>题目编号 : 238</h2>
<div style="color:#666;font-size:80%;">29 March 2009</div><br />
<div class="problem_content">
<style type="text/css">
table.p238 td { padding: 0px 3px 0px 3px; }
</style>

<p>Create a sequence of numbers using the "Blum Blum Shub" pseudo-random number generator:</p>

<center><table class="p238">
  <tr>
    <td style="text-align:right"><var>s</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /></td>
    <td>=</td>
    <td>14025256</td>
  </tr><tr>
    <td><var>s</var><img src="" style="display:none;" alt="_(" /><sub><var>n</var>+1</sub><img src="" style="display:none;" alt=")" /></td>
    <td>=</td>
    <td><var>s</var><img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" /><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> mod 20300713</td>
  </tr>
</table></center>

<p>Concatenate these numbers &thinsp;<var>s</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /><var>s</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /><var>s</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" />&hellip; to create a string <var>w</var> of infinite length.<br />
Then, <var>w</var>&thinsp;=&thinsp;<span style='font-family:courier new;font-size:12pt;color:#0000ff;'>14025256741014958470038053646&hellip;</span></p>

<p>For a positive integer <var>k</var>, if no substring of <var>w</var> exists with a sum of digits equal to <var>k</var>, <var>p</var>(<var>k</var>) is defined to be zero. If at least one substring of <var>w</var> exists with a sum of digits equal to <var>k</var>, we define <var>p</var>(<var>k</var>)&thinsp;=&thinsp;<var>z</var>, where <var>z</var> is the starting position of the earliest such substring.</p>

<p>For instance:</p>

<p>The substrings <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>1</span>, <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>14</span>, <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>1402</span>, &hellip; <br />
with respective sums of digits equal to 1, 5, 7, &hellip;<br />
start at position <b>1</b>, hence <var>p</var>(1)&thinsp;=&thinsp;<var>p</var>(5)&thinsp;=&thinsp;<var>p</var>(7)&thinsp;=&thinsp;&hellip;&thinsp;=&thinsp;<b>1</b>.</p>

<p>The substrings <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>4</span>, <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>402</span>, <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>4025</span>, &hellip;<br />
with respective sums of digits equal to 4, 6, 11, &hellip;<br />
start at position <b>2</b>, hence <var>p</var>(4)&thinsp;=&thinsp;<var>p</var>(6)&thinsp;=&thinsp;<var>p</var>(11)&thinsp;=&thinsp;&hellip;&thinsp;=&thinsp;<b>2</b>.</p>

<p>The substrings <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>02</span>, <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>0252</span>, &hellip;<br />
with respective sums of digits equal to 2, 9, &hellip;<br />
start at position <b>3</b>, hence <var>p</var>(2)&thinsp;=&thinsp;<var>p</var>(9)&thinsp;=&thinsp;&hellip;&thinsp;=&thinsp;<b>3</b>.<p>

<p>Note that substring <span style='font-family:courier new;font-size:12pt;color:#0000ff;'>025</span> starting at position <b>3</b>, has a sum of digits equal to 7, but there was an earlier substring (starting at position <b>1</b>) with a sum of digits equal to 7, so <var>p</var>(7)&thinsp;=&thinsp;1, <i>not</i> 3.</p>

<p>We can verify that, for 0&thinsp;<&thinsp;<var>k</var>&thinsp;<img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' />&thinsp;10<img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" />, <img src='images/symbol_sum.gif' width='11' height='14' alt='&sum;' border='0' style='vertical-align:middle;' />&thinsp;<var>p</var>(<var>k</var>) = 4742.</p>

<p>Find <img src='images/symbol_sum.gif' width='11' height='14' alt='&sum;' border='0' style='vertical-align:middle;' />&thinsp;<var>p</var>(<var>k</var>), for 0&thinsp;<&thinsp;<var>k</var>&thinsp;<img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' />&thinsp;2&middot;10<img src="" style="display:none;" alt="^(" /><sup>15</sup><img src="" style="display:none;" alt=")" />.</p>
</div><br />
